DAY 10 試題

問題描述

給定一個鏈結串列的頭節點 head，判斷該鏈結串列是否存在環。如果鏈結串列中某個節點可以通過不斷地跟隨 next 指針再次到達，則鏈結串列中存在環。pos 用來表示尾節點的 next 指針連接到的節點索引，注意這個值僅作為內部參考，並不作為函數的參數傳入。

若鏈結串列中存在環，則返回 true，否則返回 false。

範例 1：

• 輸入: head = [3, 2, 0, -4], pos = 1
• 輸出: true
• 解釋: 在這個鏈結串列中，尾節點連接到第一個節點（0-索引）。

範例 2：

• 輸入: head = [1, 2], pos = 0
• 輸出: true
• 解釋: 鏈結串列中的尾節點連接到第 0 個節點。

範例 3：

• 輸入: head = [1], pos = -1
• 輸出: false
• 解釋: 沒有環。

解題思路

這個問題可以使用著名的快慢指針法（Floyd 判圈演算法）來解決。具體過程如下：

1. 設置兩個指針，一個是慢指針（slow），每次移動一步；另一個是快指針（fast），每次移動兩步。

2. 如果鏈結串列中存在環，那麼快指針最終會與慢指針相遇（因為快指針會繞著環不斷追上慢指針）。如果鏈結串列沒有環，那麼快指針會首先到達鏈結串列的末尾（即 NULL），此時可以直接返回 false。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;  // 如果鏈結串列為空或只有一個節點，則不可能有環
        }
        
        ListNode *slow = head;
        ListNode *fast = head->next;

        while (slow != fast) {
            // 快指針到達結尾，則無環
            if (fast == NULL || fast->next == NULL) {
                return false;
            }
            // 慢指針移動一步，快指針移動兩步
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;  // 若兩指針相遇，則表示有環
    }
};

解法重點與分析

1. 快慢指針：此解法的核心思想是使用兩個指針，快指針每次走兩步，慢指針每次走一步。如果鏈結串列中有環，兩者最終會相遇；如果沒有環，快指針將會到達鏈結串列的末尾。

2. 時間複雜度：在最壞情況下，快指針會遍歷整個鏈結串列，而慢指針也會經過大約一半的節點。因此時間複雜度為 O(n)，其中 n 是鏈結串列的節點數。

3. 空間複雜度：由於只使用了兩個指針，因此空間複雜度為 O(1)，這使得此演算法非常高效。

總結

本題的核心在於判斷鏈結串列是否存在環，並且使用快慢指針法來達到 O(n) 的時間複雜度。通過這種方式，我們可以在不需要額外儲存空間的情況下有效地檢測鏈結串列中的環。

以上是第十天的自學內容分享，謝謝大家。